package offer.day32;

public class No53Second_GetMissingNumber {
    /*
     * 面试题53：在排序数组中查找数字
     * 题目二：0~n-1中缺失的数字
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内。
     * 在范围0~n-1内的 n个数字中有且只有一个 数字不在该数组中，请找出这个数字
     *
     *
     * 思路：时间复杂度O(logn)  空间复杂度O(1)
     * 因为0~n-1这些数字都是排序的，所以在数组中开始是从0，1，2，3，。。。，刚开始是与索引值相等的
     * 但是若某一值m缺失了，那么，m索引处就不同了，不再是m，并且m+1位置也不同了，。。。
     *
     * 因此，可以通过二分查询的算法对其进行判断：
     * 判断中间位进行判断，判断这个值是否与索引值相等：
     * 若不想等，则判断前一位是否相等，若想等，则表示这就是缺失的那一位；若不想等，则表示缺失的数字在数组的左侧
     *若相等，则缺失的数字在右侧，则继续判断右侧的数字
     *
     *
     *
     * */
    public static void main(String[] args) {
        No53Second_GetMissingNumber  s = new No53Second_GetMissingNumber();
        int[] array = {0,1,2,3,4,5,6,-1};
//        int[] array = {0,1,2,-5,3,4,5};
        System.out.println("数组中缺失的数字是： "+s.GetMissingNumber(array));
    }

    private int GetMissingNumber(int[] array) {
        if(array==null||array.length==0){
            return -1;
        }
        int left=0;
        int right=array.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(mid==array[mid]){
                left=mid+1;
            }else{
                if(mid-1==array[mid-1]){
                    return mid;
                }else{
                    right=mid-1;
                }
            }
        }
        return -1;
    }
}
